#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        int n = nums.size();
        while (fast < n)
        {
            if (nums[fast] != 0)
            {
                swap(nums[fast], nums[slow]);
                slow++;
            }
            fast++;
        }
    }
};

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        vector<int> ret(n);
        int fast = 0;
        int slow = 0;
        while (fast < n)
        {
            if (arr[slow] == 0)
            {
                ret[fast++] = 0;
                if (fast == n)
                {
                    break;
                }
                ret[fast++] = 0;
            }
            else
            {
                ret[fast++] = arr[slow];
            }
            slow++;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] = ret[i];
        }
    }
};

class Solution {
public:
    int num(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = num(n);
        while (slow != fast)
        {
            slow = num(slow);
            fast = num(num(fast));
        }
        return slow == 1 ? true : false;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0;
        int right = n - 1;
        int my_max = 0;
        while (right > left)
        {
            my_max = max(min(height[left], height[right]) * (right - left), my_max);
            if (height[left] > height[right])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return my_max;
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int right = n - 1;
        int ret = 0;
        while (right > 1)
        {
            int left = 0;
            int mid = right - 1;
            while (left < mid)
            {
                if (nums[left] + nums[mid] > nums[right])
                {
                    ret += (mid - left);
                    mid--;
                }
                else
                {
                    left++;
                }
            }
            right--;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0;
        int right = price.size() - 1;
        while (left < right)
        {
            if (price[left] + price[right] > target)
            {
                right--;
            }
            else if (price[left] + price[right] < target)
            {
                left++;
            }
            else
            {
                break;
            }
        }
        vector<int> ret;
        ret.push_back(price[left]);
        ret.push_back(price[right]);
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int left = 0;
        while (left < n - 2)
        {
            int right = n - 1;
            int mid = left + 1;
            while (mid < right)
            {
                if (nums[mid] + nums[left] + nums[right] > 0)
                {
                    right--;
                }
                else if (nums[mid] + nums[left] + nums[right] < 0)
                {
                    mid++;
                }
                else
                {
                    ret.push_back({ nums[left],nums[mid],nums[right] });
                    while (mid < right && (nums[mid] == nums[mid + 1]))
                    {
                        mid++;
                    }
                    mid++;
                }
            }
            left++;
            while (left < n - 2 && (nums[left - 1] == nums[left]))
            {
                left++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int n;
    int m;
    bool bread[10001][10001] = { true };
    void Sort(vector<vector<int>>& mat, vector<vector<int>>& board, int x, int y, int k)
    {
        if (mat[x][y] == 1 && board[x][y] == 0)
        {
            board[x][y] = k;
        }
        if (mat[x][y] == 1 && board[x][y] > k)
        {
            board[x][y] = k;
        }
        for (int i = 0; i < 4; i++)
        {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mat[x1][y1] == 1 && bread[x1][y1])
            {
                bread[x1][y1] = false;
                Sort(mat, board, x1, y1, k + 1);
                bread[x1][y1] = true;
            }
        }
    }
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        n = mat.size();
        m = mat[0].size();
        vector<vector<int>> board(n, vector<int>(m));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({ i,j });
                }
            }
        }
        while (q.size())
        {
            int x = q.front().first;
            int y = q.front().second;
            Sort(mat, board, x, y, 0);
            q.pop();
        }
        return board;
    }
};

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int>> board(n, vector<int>(m));
        vector<vector<int>> bread(n, vector<int>(m));
        queue<pair<int, int>> q;
        int dx[4] = { 0,0,-1,1 };
        int dy[4] = { -1,1,0,0 };
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({ i,j });
                }
            }
        }
        while (q.size())
        {
            int x = q.front().first;
            int y = q.front().second;
            for (int i = 0; i < 4; i++)
            {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mat[x1][y1] == 1 && bread[x1][y1] == 0)
                {
                    bread[x1][y1] = 1;
                    board[x1][y1] = board[x][y] + 1;
                    q.push({ x1,y1 });
                }
            }
            q.pop();
        }
        return board;
    }
};

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        queue<pair<int, int>> q;
        int n = image.size();
        int m = image[0].size();
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        vector<vector<bool>> bo(n, vector<bool>(m, false));
        q.push({ sr,sc });
        while (q.size())
        {
            int x = q.front().first;
            int y = q.front().second;
            for (int i = 0; i < 4; i++)
            {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !bo[x1][y1] && image[x][y] == image[x1][y1])
                {
                    q.push({ x1,y1 });
                }
            }
            image[x][y] = color;
            bo[x][y] = true;
            q.pop();
        }
        return image;
    }
};

class Solution {
public:
    int n;
    int m;
    int num = 0;
    void Sort(vector<vector<char>>& grid, vector<vector<bool>>& bk, int x, int y)
    {
        bk[x][y] = true;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        for (int i = 0; i < 4; i++)
        {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !bk[x1][y1] && grid[x1][y1] == '1')
            {
                Sort(grid, bk, x1, y1);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        n = grid.size();
        m = grid[0].size();
        vector<vector<bool>> bk(n, vector<bool>(m, false));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == '1' && !bk[i][j])
                {
                    num++;
                    Sort(grid, bk, i, j);
                }
            }
        }
        return num;
    }
};

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<long long> box;
        for (int i = 0; i < n - 1; i++)
        {
            box.emplace_back(weights[i] + weights[i + 1]);
        }
        sort(box.begin(), box.end());
        long long max_num = 0;
        long long min_num = 0;
        int l = box.size();
        for (int i = 0; i < k - 1; i++)
        {
            max_num += box[l - 1 - i];
            min_num += box[i];
        }
        return max_num - min_num;
    }
};